Zamek
Limit pamięci: 32 MB
Megachip IV Wspaniały, król Bajtocji, zamierza wydać za mąż swą urodziwą córkę, księżniczkę Adę. Zapytał ją jakiego męża chciałaby mieć. Księżniczka odpowiedziała, że jej przyszły małżonek powinien być mądry, a także ani skąpy, ani rozrzutny. Zamyślił się król nad tym, jakim to próbom powinni być poddani kandydaci na męża, aby mógł wybrać dla swej córki najlepszego z nich. Po długich dumaniach stwierdził, że najlepiej posłuży do tego zamek, który kazał był wybudować ku uciesze mieszkańców Bajtocji. Zamek składa się z dużej liczby komnat, w których zgromadzono bogactwa królestwa. Komnaty te, połączone korytarzami, mogą być zwiedzane przez poddanych w celu podziwiania wystawionych w nich wspaniałości. Za zwiedzenie komnaty trzeba uiścić pewną liczbę bajtków (bajtek jest jednostką pieniężną Bajtocji). Zwiedzanie zamku rozpoczyna się od komnaty wejściowej.
Król wręczył sakiewkę każdemu kandydatowi na męża księżniczki. W każdej sakiewce była taka sama liczba bajtków. Poprosił każdego kandydata, aby ten wybrał taką drogę, która pozwoli, poczynając od komnaty wejściowej, odwiedzić pewną liczbę komnat zamku oraz zakończyć zwiedzanie w komnacie, w której przebywa księżniczka, i wydać przy tym dokładnie kwotę, jaka była w sakiewce. Rozrzutni kandydaci, którzy wydawali po drodze zbyt dużo, nie docierali do komnaty księżniczki, skąpi natomiast zjawiali się z niepustą sakiewką i księżniczka wyprawiała ich w dalszą drogę celem opróżnienia sakiewki.
Niestety, do dziś żadnemu z kandydatów nie udało się sprostać zadaniu króla, a księżniczka Ada wciąż z utęsknieniem czeka na swój ideał. Może Ty staniesz w szranki pisząc program, który pomoże biednej księżniczce?
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis zamku, numer komnaty, w której znajduje się księżniczka i kwotę w sakiewce,
- wyznaczy ciąg komnat, przez które należy kolejno przejść, aby dojść z komnaty wejściowej do komnaty, w której znajduje się księżniczka i wydać dokładnie całą zawartość sakiewki,
- wypisze znalezioną drogę na standardowe wyjście.
Możesz założyć, że dla danych testowych taka droga zawsze istnieje. Jeśli istnieje wiele takich dróg, Twój program powinien wyznaczyć dowolną z nich.
Wejście
W pierwszym wierszu standardowego wejścia zapisanych jest pięć dodatnich liczb całkowitych , ,
, , , ,
, , ,
pooddzielanych pojedynczymi odstępami. Liczba jest równa liczbie komnat, a
liczbie korytarzy. Komnaty są ponumerowane od do .
Liczba jest numerem komnaty wejściowej, a numerem komnaty, w której znajduje się księżniczka.
Liczba określa liczbę bajtków w sakiewce. W drugim wierszu zapisanych jest
dodatnich liczb całkowitych , , pooddzielanych
pojedynczymi odstępami. Liczba jest równa opłacie za (każdorazowy) wstęp do
komnaty nr . W kolejnych wierszach zapisane są po dwie dodatnie
liczby całkowite , , , ,
oddzielone pojedynczym odstępem. Każda taka para oznacza, że komnaty o numerach
i są połączone korytarzem.
Wyjście
Twój program powinien w pierwszym (i jedynym) wierszu standardowego wyjścia zapisać
ciąg dodatnich liczb całkowitych, pooddzielanych pojedynczymi odstępami, określający
numery kolejnych komnat, przez które należy przejść, aby z komnaty wejściowej dostać
się do komnaty, w której znajduje się księżniczka i wydać dokładnie całą zawartość sakiewki.
Przykład
Dla danych wejściowych:
5 6 3 4 9
1 2 3 4 5
2 4
5 4
1 5
1 2
2 3
3 1
poprawną odpowiedzią jest:
3 2 4
Autor zadania: Zbigniew Czech.